1. Field of the Invention
The present invention constitutes a Distributed Serial Arbitration System thereof for rapidly and accurately identifying a station having the highest priority when a plurality of stations request the use of the common bus simultaneously in a multipoint, multiple access system having a common bus or communications link shared by a plurality of communication stations.
The present invention also concerns the method of self-selecting distributed arbitration that quickly identifies the station which has requested the use of the common bus service with the minimum number of needed lines in a multipoint network, as well as the method for ensuring the fairness of arbitration.
2. Description of the Prior Art
As computer systems and networks become complex and the volume of data for distributed and/or parallel processing increases, the method for allocating the common resource usage affects the overall performance of the entire system significantly.
Common resources of a system are connected via communication channels or buses. Therefore, bus arbitration plays a very important role of allocating the bus usage among stations which complete for usage of such common resources.
In computer systems, there exists various stages of buses among stations (or processors) and each processor in a multiple processor system approaches the common memory or other common resources via a common bus system.
A bus is a communication highway which connects two or more stations. There are various types of buses, from a bus which is used for communication among different parts of a system to the type used for communication among different processor systems which are located over remote areas in a network.
A bus is an electrical conductor. Simply speaking, a bus is a parallel lines that is used to transmit a specified number of signals according to its limited form of data or address. A bus normally uses DC logic levels, but may use other transmit methods such as carrier modulation and other methods that employ light waves or wireless signals so as not to permit signal quality degradation due to a transmission medium.
For a station to communicate with another, it sends a signal that calls for the other's response. Such a signal is called an `identity-address.` The station that initiates communication is referred as a master and one which responds a slave. Stations in a system can be either a master or a slave at different points in time.
Only one station can use a bus at a time. When two or more stations want to use the bus, there needs to be a procedure to grant the bus access in some way. Such a procedure is called bus arbitration.
In general, two factors are important in granting bus access to stations in any bus arbitration method. The first factor is priority. Each station has a unique priority value and the station with a higher priority obtains the bus access. The second factor is fairness. The bus access needs to be distributed fairly to all stations desiring to use the bus.
Detailed descriptions on buses and bus arbitration methods are included in references [1]-[3].
Bus arbitration methods are categorized into four types:
In Daisy Chain Arbitration methods, all stations that need bus access are arranged in a serial connection. The station with the highest priority is located in the nearest position to the arbiter and the stations are sequentially arranged according to the descending order of priority so that the one with the lowest priority is located in the furthest position. Bus access is allocated according to physical proximity to the arbiter and a priority structure is fixed in the implemented hardware.
The methods of Daisy Chain Arbitration are simple and therefore, economic. They, however, have serious drawbacks as follows: First, when stations with higher priorities dominate the bus access, fairness in bus allocation is difficult to achieve. Secondly, because stations are physically connected in a serial manner, physical lines are cumbersome to implement. Also, when a station in the middle is removed, an entire daisy chain is disconnected. Thirdly, information regarding bus arbitration is not provided in most all cases. This shortcoming makes monitoring and diagnosing of bus operations difficult.
In Centralized Parallel Arbitration, also called Independent Requesting, each station is connected to an arbiter via two independent lines for bus request and for bus permission, respectively. Thus, for n stations, there needs to be 2.sup.n lines for bus arbitration. These methods are quick. efficient, and provide fair arbitration. However, the connection between a central arbiter and each station is complex and costly. When bus requests increase sharply, a bottleneck phenomenon can occur. Also, no information on bus arbitration appears on a bus.
In Distributed Arbitration by Self Selection, also called Parallel Contention, stations requesting bus access produce their ID-address, and the station with the highest priority is determined based on bus inspection. Each station independently determines the station with the highest priority. With these methods, arbitration speed is enhanced but an abundance of lines is required, and bus access is dominated by stations with higher priorities.
In Distributed Arbitration by Collision Detection Methods, each station requests bus access independently. When a plurality of stations request bus access simultaneously, collisions can occur. And one of the colliding stations is selected and is awarded the bus access.
With existing methods it is difficult to expect both economy and fairness. Many methods experience limitations in station expandability. The present invention overcomes all of said deficiencies by developing the Distributed Serial Bus Arbitration System and implementing the apparatus thereof which identifies the station with the highest priority rapidly, realizes the fairness criterion almost perfectly by varying a station priority structure, and enables unlimited expansion in the form of multi-drops, of stations even with different transmit rates.
Furthermore, the bus arbitration method presented in the present invention can be employed for interrupt arbitration by using station ID-address which appear on the common bus. Thus, vectored interrupt arbitration is made possible.